package leetcode; /**
 * @author caifangyi
 * @date 2022/7/14
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
 *
 * 实现 WordFilter 类：
 *
 * WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
 * f(string pref, string suff) 返回词典中具有前缀prefix和后缀 suff的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
 * 
 *
 * 示例：
 *
 * 输入
 * ["WordFilter", "f"]
 * [[["apple"]], ["a", "e"]]
 * 输出
 * [null, 0]
 * 解释
 * WordFilter wordFilter = new WordFilter(["apple"]);
 * wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。
 * 
 * 提示：
 *
 * 1 <= words.length <= 104
 * 1 <= words[i].length <= 7
 * 1 <= pref.length, suff.length <= 7
 * words[i]、pref 和 suff 仅由小写英文字母组成
 * 最多对函数 f 执行 104 次调用
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/prefix-and-suffix-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class Day0745 {

    public static void main(String[] args) {
        String[] words = new String[]{"demo","apple"};
        WordFilter wordFilter = new WordFilter(words);
        int f = wordFilter.f("a", "e");// 返回
        System.out.println(f);
    }

    static class WordFilter {

        Map<String, Integer> map = new HashMap<>();

        public WordFilter(String[] words) {
            //空间换时间，建立索引表
            for (int index = 0 ; index < words.length; index++) {
                String word = words[index];
                int length = word.length();
                for(int i = 1;i <= length; i++){
                    for(int j = 1; j <= length; j++){
                        map.put(word.substring(0, i)+"#"+word.substring(length-j, length), index);
                    }
                }
            }
        }

        public int f(String pref, String suff) {

           return map.getOrDefault(pref+"#"+suff, -1);
        }
    }
}



